#include<iostream>
using namespace std;
const int N=1e5+10,M=1e6+10;
int elem[N],ne[N],id,n,h;
int mp[M];
void init(){
	id++;
	elem[id]=1;
	mp[1]=id;
	ne[id]=ne[h];
	ne[h]=id;
}
void insert(int p,int x){
	id++;
	elem[id]=x;
	mp[x]=id;
	int q=mp[p];
	ne[id]=ne[q];
	ne[q]=id;
}
int find(int x){
	int id=mp[x];
	if(ne[id]!=0){
		return elem[ne[id]];
	}else{
		return 0;
	}
}
void erase(int x){
	int id=mp[x];
	int tmp=elem[ne[id]];
	ne[id]=ne[ne[id]];
	mp[tmp]=0;
}
int main(){
	init();
	cin>>n;
	for(int i=1;i<=n;i++){
		int op;
		cin>>op;
		if(op==1){
			int x,y;
			cin>>x>>y;
			insert(x,y);
		}else if(op==2){
			int z;
			cin>>z;
			cout<<find(z)<<endl;
		}else{
			int m;
			cin>>m;
			erase(m); 
		}
	}
	return 0;
} 
